The present invention relates to trace-based compiler techniques, and more specifically to a multi-level compilation technique applied to trace-based compilers.
Hitherto, trace-based compilers that use frequently executed code sequences hereinafter, referred to as “traces”, as basic units for compilation and execution have been known, for example, see P. Wu, H. Hayashizaki, H. Inoue, and T. Nakatani, “Reducing Trace Selection Footprint for Large-scale Java Applications with no Performance Loss”, in Proceedings of the ACM Object-Oriented Programming, Systems, Languages & Applications, pp. 789-804, 2011, H. Inoue, H. Hayashizaki, P. Wu, and T. Nakatani, “A Trace-based Java JIT Compiler Retrofitted from a Method-based Compiler”, in Proceedings of the International Symposium on Code Generation and Optimization, pp. 246-256, 2011, and H. Hayashizaki, P. Wu, H. Inoue, M. Serrano, and T. Nakatani, “Improving the Performance of Trace-based Systems by False Loop Filtering”, In Proceedings of Sixteenth International Conference on Architectural Support for Programming Languages and Operating Systems, pp. 405-418, 2011.
Trace selection is an essential key for trace-based compilers. Generating longer traces increases the opportunities for compiler optimization and reduces the overhead of transitions between compiled traces. However, generating long traces often causes generation of duplicated traces. This increases the code size and the compilation time, and degrades the startup performance, for example, see Non-patent Literature 1.
Generating longer traces in trace-based compilers is similar to expanding the compilation scope by aggressively performing method inlining in method-based compilers. In systems using method-based just-in-time (JIT) compilers, adaptive multi-level compilation techniques are widely used in order to achieve both quick startup and high peak performance, for example see Michael Paleczny, Christopher Vick, and Cliff Click, “The Java Hotspot™ Server Compiler”, in Proceedings of the USENIX Java Virtual Machine Research and Technology Symposium, pp. 1-12, 2001, N. Greevski, A. Kielstra, K. Stoodley, M. Stoodley, and V. Sundaresan, “Java just-in-time compiler and virtual machine improvements for server and middleware applications”, In Proceedings of the USENIX Virtual Machine Research and Technology Symposium, pp. 151-162, 2004, T. Suganuma, T. Yasue, M. Kawahito, H. Komatsu, and T. Nakatani, “A dynamic optimization framework for a Java just-in-time compiler”, in Proceedings of the ACM Conference on Object-Oriented Programming Systems, Languages, and Applications, pp. 180-195, 2001, M. Arnold, S. Fink, D. Grove, M. Hind, and P. F. Sweeney, “Adaptive optimization in the Jalapeno JVM”, in Proceedings of the ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, pp. 47-65, 2000, U. Holzle and D. Ungar, “A third generation self implementation: Reconciling responsiveness with performance”, in Proceedings of the ACM conference on Object-Oriented Programming, Systems, Languages, and Applications, pp. 229-243, 1994, and U.S. Pat. No. 7,386,686.
In adaptive multi-level compilation techniques, compilation is performed at a low optimization level during startup of a program. After the startup ends, methods that use more execution time are found through profiling and then recompilation is performed on the methods at a higher optimization level. It is desired that trace-based compilers also perform multi-level compilation to increase both startup speed and peak performance.
In the list of related-art literatures below, V. Bala, E. Duesterwald, and S. Banerjia, “Dynamo: A Transparent Runtime Optimization System”, in Proceedings of the ACM Programming Language Design and Implementation, pp. 1-12, 2000 is listed as the background art regarding an optimization technique that links traces with each other, trace linking optimization, which is used in an embodiment of the present invention.
Also, M. Hirzel and T. M. Chilimbi, “Bursty tracing: a framework for low-overhead temporal profiling”, in Proceedings of the 4th Workshop on Feedback-Directed and Dynamic Optimization, pp. 117-126, 2001 is listed as the background art regarding a bursty tracing technique from which a technique used in the embodiment of the present invention is derived. In addition, M. Hirzel and T. M. Chilimbi, “Bursty tracing: a framework for low-overhead temporal profiling”, in Proceedings of the 4th, Workshop on Feedback-Directed and Dynamic Optimization, pp. 117-126, 2001, M. Bebenita, F. Brandner, M. Fahndrich, F. Logozzo, W. Schulte, N. Tillmann, and H. venter, “SPUR: A trace-based JIT compiler for CIL”, in Proceedings of the ACM international conference on Object oriented programming systems languages and applications, pp. 708-725, 2010, and M. Bebenita, M. Chang, G. Wagner, A. Gal, C. Wimmer, and M. Franz, “Trace-based compilation in execution environments without interpreters”, in Proceedings of the 8th International Conference on the Principles and Practice of Programming in Java, pp. 59-68, 2010 are listed as existing tracing techniques that support recompilation.
However, unlike the present invention, recompilation described in C. Haubl et al., is recompilation for correcting frequently aborting traces and is not upgrade recompilation. Also, the initial compilation described in Non-patent Literatures M. Bebenita et al. and M. Bebenita et al. is performed to compile code inserted for execution monitoring. Recompilation described in these literatures is equivalent to ordinary compilation and is not upgrade recompilation, unlike the present invention.